// Package _1_DP No-1-Feb
// @Title _1_DP
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/27 15:18
// @Create  2021/9/27 15:18
package _1_DP

/**
动态规划解决斐波拉契数列
*/
func FebRecursion(a int) int {
	// 这是使用傻递归的方式做
	//return recursionProcess(a)
	// 使用状态数组，记忆化搜索
	return dpArrProcess(a)
}

// 使用傻递归的方式解决斐波拉契数列
func recursionProcess(a int) int {
	if a <= 2 {
		return 1
	}
	return FebRecursion(a-1) + FebRecursion(a-2)
}

// 动态规划暂存状态的方式
func dpArrProcess(a int) int {
	dpArr := make([]int, a+1)
	for i := 0; i <= a; i++ {
		if i <= 2 {
			dpArr[i] = 1
		} else {
			dpArr[i] = dpArr[i-1] + dpArr[i-2]
		}
	}
	return dpArr[a]
}
